package com.liuzhilong.infrastructure.framework.algorithms.algorithms;

/**
 * 寻找中位数
 * @author longandai@163.com
 */
public class MedianFind {
    /**
     * <h1>寻找两个正序数组的中位数</h1>
     * <p>
     *     给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。<br>
     *     进阶：设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题
     * </p>
     * <h2>思路</h2>
     * 循环(m+n)/2 次，使用left和right两个变量保存前一次和本次的值。如果奇数 返回right，如果偶数 返回right
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int lengthAll = m+n;
        boolean isOdd = (lengthAll&1)==1;
        Integer left = null, right = null;
        int mIndex=0,nIndex=0;
        for(int i =0;i<=lengthAll/2;i++){
            //设置right的值到left上
            left = right;
            if(mIndex>=m){
                right = nums2[nIndex++];
                continue;
            }
            if(nIndex>=n){
                right = nums1[mIndex++];
                continue;
            }
            //两边都没有到头 设置小的一边 并且把小的指针+1
            if(nums1[mIndex]<nums2[nIndex]){
                right = nums1[mIndex++];
            }else {
                right = nums2[nIndex++];
            }
        }
        if(isOdd){
            return right;
        }else{
            return (left+right)/2.0;
        }
    }
    /**
     * <h1>寻找两个正序数组的中位数</h1>
     * <p>
     *     给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。<br>
     *    时间复杂度为 O(log (m+n)) 的算法
     * </p>
     * <h2>思路</h2>
     * log方法一般是二分法，考虑用二分法判断的思路为
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArraysLog(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int lengthAll = m+n;
        boolean isOdd = (lengthAll&1)==1;
        Integer left = null, right = null;
        int mIndex=0,nIndex=0;
        for(int i =0;i<=lengthAll/2;i++){
            //设置right的值到left上
            left = right;
            if(mIndex>=m){
                right = nums2[nIndex++];
                continue;
            }
            if(nIndex>=n){
                right = nums1[mIndex++];
                continue;
            }
            //两边都没有到头 设置小的一边 并且把小的指针+1
            if(nums1[mIndex]<nums2[nIndex]){
                right = nums1[mIndex++];
            }else {
                right = nums2[nIndex++];
            }
        }
        if(isOdd){
            return right;
        }else{
            return (left+right)/2.0;
        }
    }
    public static void main(String[] args) {
        int[] m = new int[]{};
        int[] n= new int[]{2,2,4};
        System.out.println(findMedianSortedArrays(m,n));


    }

}
